/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/reverse-linked-list-ii
   @Language: C++
   @Datetime: 16-02-09 08:25
   */

/**
 * Definition of singly-linked-list:
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
	/**
	 * @param head: The head of linked list.
	 * @param m: The start position need to reverse.
	 * @param n: The end position need to reverse.
	 * @return: The new head of partial reversed linked list.
	 */
	ListNode *reverseBetween(ListNode *head, int m, int n) {
		// write your code here
		ListNode H{0,head}, *tail=&H, *curr;
		for (int i=1; i<m; ++i) tail=tail->next;
		head = tail->next;
		curr = head->next;
		for (int i=m; i<n; ++i) {
			head->next = curr->next;
			curr->next = tail->next;
			tail->next = curr;
			curr = head->next;
		}
		return H.next;
	}
};
